#include <iostream>

using namespace std;
struct ListNode {
    int val;
    struct ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
    
};
ListNode* reverseList(ListNode* head, int size)
{
    if (!head)
        return nullptr;
    ListNode* per = nullptr;
    ListNode* cur = head;
    ListNode* tail = head;
    while (cur && size--)
    {
        ListNode* next = cur->next;
        cur->next = per;
        per = cur;
        cur = next;
    }
    tail->next = cur;
    return per;
}
ListNode* reverseBetween(ListNode* head, int m, int n) {
    int size = n - m + 1;
    ListNode* ret = head;
    ListNode phead(0);
    phead.next = head;
    ListNode* pre = &phead;
    while (--m)
    {
        pre = pre->next;
    }
    pre->next = reverseList(pre->next, size);
    return ret;
}
int main()
{
    ListNode* Listnode1 = new ListNode(1);
    ListNode* Listnode2 = new ListNode(2);
    ListNode* Listnode3 = new ListNode(3);
    ListNode* Listnode4 = new ListNode(4);
    ListNode* Listnode5 = new ListNode(5);

    Listnode1->next = Listnode2;
    Listnode2->next = Listnode3;
    Listnode3->next = Listnode4;
    Listnode4->next = Listnode5;
    reverseBetween(Listnode1, 2, 4);
    return 0;
}

